原题链接:[POJ 2686] Traveling by Stagecoach
原题大意:有个城市,张票.给定了起点和终点,以及两个城市之间的距离,假如两个城市之间是联通的,那么在使用一张车票的时候,会有只马的车载你到另一个城市,需要的时间是距离除马的数量.每张车票只能用一次现求从起点到终点最少时间是多少.
数据范围:
思路
由于数据量很小,在这种情况下考虑到指数级的算法可能的就是搜索和状压.这个题如果去掉车票的限制就是一个普通的最短路问题.如果要加入这个车票的限制,则在递推的时候也要把整个车票的状态全考虑进去,因此这就比较明显是一个状态压缩的形式:把所有的车票用二进制数压缩,表示用了,将整个状态丢进去考虑再求最短路即可.
不过这题还有一个性质:可以发现从起点一直往外拓展的话,整个车票集合是只增不减的,也就是说如果把状态看成点,转移看成边,那么整个图是一个,即可以直接递推得到最后的答案.
状态设计
状态:$$f[S][v]Sv$城市时最少要消耗多少时间,集合里如果是表示已经用了,表示没有用.
入口:一开始在城市,自然为.由于要求最小值,因此其他为正无穷.
出口:其中~表示任意的值,即只要能到即可.
转移:首先遍历起点,再遍历集合里每个元素,看哪个车票还没用,记为.再枚举谁是下一个到达的城市.这个过程就是从到使用号车票.则实际产生的代价就是.而后一个状态,也即是用掉了车票的状态记作.表达式为
代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
int n,m,p,S,T;
const int N = 100,M = 10000,_N = 1 << 8;
const double INF = 1e12;
int dist[N][N];
double f[_N][N];
int t[N];
int main()
{
while((scanf("%d%d%d%d%d",&n,&m,&p,&S,&T) == 5))
{
if(!n && !m && !p && !S && !T) break;
--S;--T;
for(int i = 0;i < n;++i) scanf("%d",&t[i]);
for(int i = 0;i < 1 << n;++i) fill(f[i],f[i] + m,INF);
for(int i = 0;i < m;++i) fill(dist[i],dist[i] + m,-1);
for(int i = 0;i < p;++i)
{
int u,v,w;scanf("%d%d%d",&u,&v,&w);
--u;--v;
dist[u][v] = dist[v][u] = w;
}
f[0][S] = 0;
double res = INF;
for(int state = 0;state < 1 << n;++state)
{
for(int v = 0;v < m;++v)
{
for(int i = 0;i < n;++i)
{
if(!(state >> i & 1))
{
for(int u = 0;u < m;++u)
{
if(dist[v][u] >= 0)
{
double rc = (double)dist[v][u] / t[i];
int _state = state | (1 << i);
f[_state][u] = min(f[_state][u],f[state][v] + rc);
}
}
}
}
}
res = min(res,f[state][T]);
}
if(res == INF) printf("Impossible\n");
else printf("%.3lf\n",res);
}
return 0;
}